package org.hhchat.leetcode.array;

public class code215_medium {
    static class Solution {
        public int findKthLargest(int[] nums, int k) {
            return helper(0, nums.length-1, nums, k -1 );

        }

        public int helper(int l,int h, int[] arr, int k){
            int[] bound = partition(arr, k, l, h);
            if(l<=h && k>=0 && k<arr.length){

                if(bound[0] > k){
                    return helper(l, bound[0]-1, arr, k);
                }else if(bound[1] < k){
                    return helper(bound[1]+1 , h, arr, k);
                }else{
                    return arr[k];
                }
            }
            return -1;

        }

        public int[] partition(int[] arr, int k, int l,int h){
            int key = arr[l];
            int i=l;
            while(i<=h){
                if(arr[i] == key){
                    i++;
                }else if(arr[i] > key){
                    swap(arr, l++, i++);
                }else{
                    swap(arr, h--, i);
                }
            }
            int[] range = new int[2];
            range[0] = l;
            range[1] = h;
            return range;
        }

        public void swap(int[] arr, int l ,int h){
            int temp = arr[l];
            arr[l] = arr[h];
            arr[h] = temp;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1};
        System.out.println(solution.findKthLargest(arr,1));
    }
}
